package com.cty._05_Ability._59_01_MaxInSlidingWindow;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @Auther: cty
 * @Date: 2020/7/24 8:55
 * @Description: 面试题59（一）：滑动窗口的最大值
 * 题目：给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。例如，
 * 如果输入数组{2, 3, 4, 2, 6, 2, 5, 1}及滑动窗口的大小3，那么一共存在6个
 * 滑动窗口，它们的最大值分别为{4, 4, 6, 6, 6, 5}。
 * @version: 1.0
 */
public class MaxInSlidingWindow {

    public static List<Integer> maxInSlidingWindow(List<Integer> array, int window){
        if(array==null || array.size()==0 || window>array.size() || window<1)
            return null;

        Deque<Integer> indexDeque = new ArrayDeque<>(window);
        List<Integer> maxArray = new ArrayList<>(array.size());

        for(int i=0; i<window; i++){
            while(!indexDeque.isEmpty() && array.get(i)>=array.get(indexDeque.peekLast()))
                indexDeque.removeLast();
            indexDeque.addLast(i);
        }

        for(int i=window; i<array.size(); i++){
            maxArray.add(array.get(indexDeque.peekFirst()));

            while(!indexDeque.isEmpty() && array.get(i)>=array.get(indexDeque.peekLast()))
                indexDeque.removeLast();  // 右端逐个移除所有值
            if(!indexDeque.isEmpty() && indexDeque.peekFirst()<=i-3)
                indexDeque.removeFirst();  // 左端移除最大值
            indexDeque.addLast(i);
        }
        maxArray.add(array.get(indexDeque.peekFirst()));
        return maxArray;
    }  // end maxInSlidingWindow()

}  // end class
